def quicksort(arr):
    n = len(arr)
    if (n <= 1): return arr

    pivot = arr[0]
    lo, eq, hi = [], [pivot], []
    
    for n in arr[1:]:
        if n < pivot:
            lo.append(n)
        elif n > pivot:
            hi.append(n)
        else:
            eq.append(n)
    
    lo = quicksort(lo)
    hi = quicksort(hi)
    return lo + eq + hi


if __name__ == "__main__":
    print(quicksort([9, 2, 8]))
    print(quicksort([3, 6, 0, 4]))
    print(quicksort([1, 8, 7, 3, 6, 0, 4]))
